class Solution {
public:
    vector<vector<string>> ans;
    bool check(string& s) {
        int i = 0, j = s.size() - 1;
        while (i < j) {
            if (s[i] != s[j])
                return false;
            ++i;
            --j;
        }
        return true;
    }
    void dfs(int pos, vector<string>& v, const string& s) {
        if (pos == s.size()) {
            ans.push_back(v);
            return;
        }
        for (int i = pos; i < s.size(); i++) {
            string ss = s.substr(pos, i - pos + 1);
            if (check(ss)) {
                v.push_back(ss);
                dfs(i + 1, v, s);
                v.pop_back();
            }
        }
    }
    vector<vector<string>> partition(string s) {
        vector<string> v;
        dfs(0, v, s);
        return ans;
    }
};